{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Ways to Split Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: waysToSplitArray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #分割数组的方案数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始长度为 <code>n</code>&nbsp;的整数数组&nbsp;<code>nums</code>&nbsp;。<br />\n",
    "<span style=\"\">如果以下描述为真，那么</span><span style=\"\"> </span><code>nums</code>&nbsp;在下标 <code>i</code>&nbsp;处有一个 <strong>合法的分割</strong>&nbsp;：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>前&nbsp;<code>i + 1</code>&nbsp;个元素的和 <strong>大于等于</strong>&nbsp;剩下的&nbsp;<code>n - i - 1</code>&nbsp;个元素的和。</li>\n",
    "\t<li>下标 <code>i</code>&nbsp;的右边 <strong>至少有一个</strong>&nbsp;元素，也就是说下标&nbsp;<code>i</code>&nbsp;满足&nbsp;<code>0 &lt;= i &lt; n - 1</code>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回&nbsp;<code>nums</code>&nbsp;中的&nbsp;<strong>合法分割</strong>&nbsp;方案数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [10,4,-8,7]\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>\n",
    "总共有 3 种不同的方案可以将 nums 分割成两个非空的部分：\n",
    "- 在下标 0 处分割 nums 。那么第一部分为 [10] ，和为 10 。第二部分为 [4,-8,7] ，和为 3 。因为 10 &gt;= 3 ，所以 i = 0 是一个合法的分割。\n",
    "- 在下标 1 处分割 nums 。那么第一部分为 [10,4] ，和为 14 。第二部分为 [-8,7] ，和为 -1 。因为 14 &gt;= -1 ，所以 i = 1 是一个合法的分割。\n",
    "- 在下标 2 处分割 nums 。那么第一部分为 [10,4,-8] ，和为 6 。第二部分为 [7] ，和为 7 。因为 6 &lt; 7 ，所以 i = 2 不是一个合法的分割。\n",
    "所以 nums 中总共合法分割方案受为 2 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [2,3,1,0]\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>\n",
    "总共有 2 种 nums 的合法分割：\n",
    "- 在下标 1 处分割 nums 。那么第一部分为 [2,3] ，和为 5 。第二部分为 [1,0] ，和为 1 。因为 5 &gt;= 1 ，所以 i = 1 是一个合法的分割。\n",
    "- 在下标 2 处分割 nums 。那么第一部分为 [2,3,1] ，和为 6 。第二部分为 [0] ，和为 0 。因为 6 &gt;= 0 ，所以 i = 2 是一个合法的分割。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>-10<sup>5</sup> &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-ways-to-split-array](https://leetcode.cn/problems/number-of-ways-to-split-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-ways-to-split-array](https://leetcode.cn/problems/number-of-ways-to-split-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[10,4,-8,7]', '[2,3,1,0]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplitArray(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        left = 0\n",
    "        right = sum(nums)\n",
    "        for i in range(len(nums)-1):\n",
    "            left += nums[i]\n",
    "            right -= nums[i]\n",
    "            if left >= right:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplitArray(self, nums: List[int]) -> int:\n",
    "        sums = sum(nums)\n",
    "        n = 0\n",
    "        res = 0\n",
    "        for i in nums[:-1]:\n",
    "            n+=i \n",
    "            if n>=sums-n:\n",
    "                res+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplitArray(self, nums: List[int]) -> int:\n",
    "        target = sum(nums) / 2\n",
    "        return sum(s >= target for s in accumulate(nums[:-1]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplitArray(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        # for i in range(len(nums) - 1):\n",
    "        #     leftNums = nums[0:i+1]\n",
    "        #     rightNums = nums[i+1:-1]\n",
    "        #     if sum(leftNums) >= sum(rightNums):\n",
    "        #         ans += 1\n",
    "        left = 0\n",
    "        right = sum(nums)\n",
    "        for i in range(len(nums)-1):\n",
    "            left += nums[i]\n",
    "            right -= nums[i]\n",
    "            if left >= right:\n",
    "                ans += 1\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplitArray(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        left = 0\n",
    "        right = sum(nums)\n",
    "        for i in range(len(nums)-1):\n",
    "            left += nums[i]\n",
    "            right -= nums[i]\n",
    "            if left >= right:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplitArray(self, nums: List[int]) -> int:\n",
    "        cnt =0\n",
    "        F = 0\n",
    "        T = sum(nums)/2\n",
    "        for i in range(len(nums)-1):\n",
    "            F += nums[i]\n",
    "            if F >= T:\n",
    "                cnt += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplitArray(self, nums: List[int]) -> int:\n",
    "        n, left, right = len(nums), 0, sum(nums)\n",
    "        ans = 0\n",
    "        for i in range(n - 1):\n",
    "            left += nums[i]\n",
    "            right -= nums[i]\n",
    "            if left >= right:\n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplitArray(self, nums: List[int]) -> int:\n",
    "        sum1 = 0\n",
    "        total = sum(nums)\n",
    "        count = 0\n",
    "        for i in range(len(nums)-1):\n",
    "            sum1+=nums[i]\n",
    "            total-=nums[i]\n",
    "            if sum1>=total:\n",
    "                count+=1\n",
    "        return count\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplitArray(self, nums: List[int]) -> int:\n",
    "        ans, presum, postsum = 0, 0, sum(nums)\n",
    "        for i in nums[:-1]:\n",
    "            presum += i\n",
    "            postsum -= i\n",
    "            ans += presum >= postsum\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplitArray(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        x=sum(nums)\n",
    "        ans=0\n",
    "        s=0\n",
    "        for i in range(n-1):\n",
    "            s+=nums[i]\n",
    "            if 2*s>=x:\n",
    "                ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplitArray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        su = sum(nums)\n",
    "        ans = 0\n",
    "        pref = 0\n",
    "        for i in range(n - 1):\n",
    "            pref += nums[i]\n",
    "            if pref >= su - pref:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplitArray(self, nums: List[int]) -> int:\n",
    "\n",
    "        suffix = sum(nums)\n",
    "\n",
    "        pre = 0\n",
    "        ans = 0\n",
    "        for i in range(len(nums) - 1):\n",
    "            pre += nums[i]\n",
    "            suffix -= nums[i]\n",
    "\n",
    "            if pre >= suffix: \n",
    "                ans += 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplitArray(self, nums: List[int]) -> int:\n",
    "        s=sum(nums)\n",
    "        count=0\n",
    "        res=0\n",
    "        for i in range(len(nums)-1):\n",
    "            res+=nums[i]\n",
    "            if 2*res>=s:\n",
    "                count+=1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplitArray(self, nums: List[int]) -> int:\n",
    "        sum1 = 0\n",
    "        total = sum(nums)\n",
    "        count = 0\n",
    "        for i in range(len(nums)-1):\n",
    "            sum1+=nums[i]\n",
    "            total-=nums[i]\n",
    "            if sum1>=total:\n",
    "                count+=1\n",
    "        return count\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplitArray(self, nums: List[int]) -> int:\n",
    "        tot = sum(nums)\n",
    "        s = ret = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n - 1):\n",
    "            s += nums[i]\n",
    "            if s >= tot - s:\n",
    "                ret += 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplitArray(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        total = sum(nums)\n",
    "        s = 0\n",
    "        for i in range(len(nums) - 1):\n",
    "            s += nums[i]\n",
    "            if s * 2 >= total:\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplitArray(self, nums: List[int]) -> int:\n",
    "        cnt =0\n",
    "        F = 0\n",
    "        R = sum(nums)\n",
    "        for i in range(len(nums)-1):\n",
    "            F += nums[i]\n",
    "            R -= nums[i]\n",
    "            if F >= R:\n",
    "                cnt += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplitArray(self, nums: List[int]) -> int:\n",
    "        re = 0\n",
    "        l = 0\n",
    "        r = sum(nums)\n",
    "        for i in range(len(nums)-1):\n",
    "            l += nums[i]\n",
    "            r -= nums[i]\n",
    "            if l >= r:\n",
    "                re += 1\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplitArray(self, nums: List[int]) -> int:\n",
    "        count = 0\n",
    "        left, right = 0, sum(nums)\n",
    "        for i in range(len(nums) - 1):\n",
    "            if left + nums[i] >= right - nums[i]:\n",
    "                count += 1\n",
    "            left += nums[i]\n",
    "            right -= nums[i]\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplitArray(self, nums: List[int]) -> int:\n",
    "        s = sum(nums)\n",
    "        l = 0\n",
    "        res = 0 \n",
    "        for i in range(len(nums)-1):\n",
    "            l += nums[i]\n",
    "            if  l >= s - l:\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplitArray(self, nums: List[int]) -> int:\n",
    "        SUM=sum(nums)\n",
    "        res,ans=0,0\n",
    "        for i in range(len(nums)-1):\n",
    "            ans+=nums[i]\n",
    "            if 2*ans>=SUM:\n",
    "                res+=1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # * 枚举 + 前缀和\n",
    "    def waysToSplitArray(self, nums: List[int]) -> int:\n",
    "        n, left, right = len(nums), 0, sum(nums)\n",
    "        ans = 0\n",
    "        for i in range(n - 1):\n",
    "            left += nums[i]\n",
    "            right -= nums[i]\n",
    "            if left >= right:\n",
    "                ans += 1\n",
    "                \n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplitArray(self, nums: List[int]) -> int:\n",
    "        n, left, right = len(nums), 0, sum(nums)\n",
    "        ans = 0\n",
    "        for i in range(n - 1):\n",
    "            left += nums[i]\n",
    "            right -= nums[i]\n",
    "            if left >= right:\n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "\n",
    "    def waysToSplitArray(self, nums: List[int]) -> int:\n",
    "        sumleft, sumright, ans = 0, sum(nums), 0\n",
    "        for i in range(len(nums) - 1):\n",
    "            sumleft += nums[i]\n",
    "            sumright -= nums[i]\n",
    "            if sumleft >= sumright: \n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplitArray(self, nums: List[int]) -> int:\n",
    "        SUM=sum(nums)\n",
    "        res,ans=0,0\n",
    "        for i in range(len(nums)-1):\n",
    "            ans+=nums[i]\n",
    "            if 2*ans>=SUM:\n",
    "                res+=1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplitArray(self, nums: List[int]) -> int:\n",
    "        cnt =0\n",
    "        F = 0\n",
    "        T = sum(nums)/2\n",
    "        for i in range(len(nums)-1):\n",
    "            F += nums[i]\n",
    "            if F >= T:\n",
    "                cnt += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplitArray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        prefix = 0\n",
    "        suffix = sum(nums)\n",
    "        ans = 0\n",
    "        for i in range(n-1):\n",
    "            prefix += nums[i]\n",
    "            suffix -= nums[i]\n",
    "            if prefix >= suffix:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplitArray(self, nums: List[int]) -> int:\n",
    "        s = sum(nums)\n",
    "        n = len(nums)\n",
    "        ans = cnt = 0\n",
    "        for i in range(n-1):\n",
    "            cnt += nums[i]\n",
    "            s -= nums[i]\n",
    "            if cnt >= s:\n",
    "                ans += 1\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplitArray(self, nums: List[int]) -> int:\n",
    "        s = sum(nums)\n",
    "        cur = 0\n",
    "        res = 0\n",
    "        for i in range(len(nums) - 1):\n",
    "            cur += nums[i]\n",
    "            if cur >= s / 2:\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplitArray(self, nums: List[int]) -> int:\n",
    "        s = sum(nums)\n",
    "        n = len(nums)\n",
    "        pre = 0\n",
    "        ans = 0\n",
    "        for i in range(n - 1):\n",
    "            pre += nums[i]\n",
    "            if pre >= s - pre:\n",
    "                ans += 1\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplitArray(self, nums: List[int]) -> int:\n",
    "        n, left, right = len(nums), 0, sum(nums)\n",
    "        ans = 0\n",
    "        for i in range(n - 1):\n",
    "            left += nums[i]\n",
    "            right -= nums[i]\n",
    "            if left >= right:\n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplitArray(self, nums: List[int]) -> int:\n",
    "        target = sum(nums) / 2\n",
    "        return sum(i >= target for i in accumulate(nums[:-1]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "\n",
    "    def waysToSplitArray(self, nums: List[int]) -> int:\n",
    "        sumleft, sumright, ans = 0, sum(nums), 0\n",
    "        for i in range(len(nums) - 1):\n",
    "            sumleft += nums[i]\n",
    "            sumright -= nums[i]\n",
    "            if sumleft >= sumright: \n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplitArray(self, nums: List[int]) -> int:\n",
    "        cnt =0\n",
    "        F = 0\n",
    "        T = sum(nums)/2\n",
    "        for i in range(len(nums)-1):\n",
    "            F += nums[i]\n",
    "            if F >= T:\n",
    "                cnt += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplitArray(self, nums: List[int]) -> int:\n",
    "        s=sum(nums)\n",
    "        cur=0\n",
    "        ans=0\n",
    "        for i in range(len(nums)-1):\n",
    "            cur+=nums[i]\n",
    "            s-=nums[i]\n",
    "            if cur>=s:\n",
    "                ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplitArray(self, nums: List[int]) -> int:\n",
    "        all_sum = sum(nums)\n",
    "        n = len(nums)\n",
    "        cnt = 0\n",
    "        left_sum = 0\n",
    "        for i in range(n-1):\n",
    "            left_sum += nums[i]\n",
    "            if left_sum >= all_sum - left_sum:\n",
    "                cnt += 1\n",
    "\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def waysToSplitArray(self, nums: List[int]) -> int:\r\n",
    "        n = len(nums)\r\n",
    "        lf,rt = 0,sum(nums)\r\n",
    "        ans = 0\r\n",
    "        for i in range(n-1):\r\n",
    "            lf += nums[i]\r\n",
    "            rt -= nums[i]\r\n",
    "            if lf >= rt:\r\n",
    "                ans += 1\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplitArray(self, nums: List[int]) -> int:\n",
    "        for i in range(1, len(nums)):\n",
    "            nums[i] += nums[i-1]\n",
    "        cor = (nums[i] + 1) // 2\n",
    "        ans = 0\n",
    "        for i in range(len(nums)-1):\n",
    "            if nums[i] >= cor:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplitArray(self, nums: List[int]) -> int:\n",
    "        sum_right = 0\n",
    "        sum_left = 0\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            sum_right += nums[i]\n",
    "        for i in range(len(nums) - 1):\n",
    "            sum_right -= nums[i]\n",
    "            sum_left += nums[i]\n",
    "            print(sum_left)\n",
    "            print(sum_right)\n",
    "            if sum_left >= sum_right:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplitArray(self, nums: List[int]) -> int:\n",
    "        sumleft, sumright, cnt = 0, sum(nums), 0\n",
    "        for i in range(len(nums) - 1):  # 遍历到倒数第二个元素\n",
    "            sumleft += nums[i]  # 前 i+1 个元素的和\n",
    "            sumright -= nums[i]  # 剩下的元素的和\n",
    "            if sumleft >= sumright:  # 检查是否满足条件\n",
    "                cnt += 1  # 如果满足，增加计数\n",
    "        return cnt\n",
    "\n",
    "# 测试代码\n",
    "nums = [10,4,-8,7]\n",
    "sol = Solution()\n",
    "print(sol.waysToSplitArray(nums))  # 应输出 2\n",
    "\n",
    "nums = [2,3,1,0]\n",
    "print(sol.waysToSplitArray(nums))  # 应输出 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplitArray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        prefix_sum = [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            prefix_sum[i + 1] = prefix_sum[i] + nums[i]\n",
    "\n",
    "        valid_splits = 0\n",
    "        for i in range(n - 1):\n",
    "            left_sum = prefix_sum[i + 1]\n",
    "            right_sum = prefix_sum[n] - left_sum\n",
    "            if left_sum >= right_sum:\n",
    "                valid_splits += 1\n",
    "\n",
    "        return valid_splits"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplitArray(self, nums: List[int]) -> int:\n",
    "        presum_list = [0] *len(nums)\n",
    "        presum_list[0] = nums[0]\n",
    "        for i in range(1, len(nums)):\n",
    "            presum_list[i] = presum_list[i-1] + nums[i] \n",
    "        res = 0\n",
    "        for i, x in enumerate(presum_list):\n",
    "            if x >= presum_list[-1] -x and i != len(nums) - 1:\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplitArray(self, nums: List[int]) -> int:\n",
    "        prefix = [0] * (len(nums)+1)\n",
    "        for i in range(1, len(prefix)):\n",
    "            prefix[i] = prefix[i-1] + nums[i-1]\n",
    "        _sum = prefix[-1]\n",
    "        cnt = 0\n",
    "        for wall in range(1, len(prefix)-1):\n",
    "            left = prefix[wall]\n",
    "            right = _sum - left\n",
    "            if left >= right:\n",
    "                cnt += 1\n",
    "        return cnt\n",
    "\n",
    "\n",
    "'''\n",
    "题意分析：\n",
    "\n",
    "我们主要找一个wall，其中左边的元素和要大于等于右边的元素和\n",
    "\n",
    "可以实现计算前缀和然后使用整体的和减去前面的和，就是右边的和\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplitArray(self, nums: List[int]) -> int:\n",
    "\n",
    "        # s=sum(nums)\n",
    "        # dp1=[]\n",
    "        # dp2=[]\n",
    "        # t=0\n",
    "        # res=0\n",
    "        # for i in nums:\n",
    "        #     t+=i\n",
    "        #     dp1.append(t)\n",
    "        #     dp2.append(s-t)\n",
    "        # for i in range(len(dp1)-1):\n",
    "        #     if dp1[i]>=dp2[i]:\n",
    "        #         res+=1\n",
    "        # return res\n",
    "\n",
    "        s=sum(nums)\n",
    "        dp=[]\n",
    "        t=0\n",
    "        res=0\n",
    "        for i in nums:\n",
    "            t+=i\n",
    "            dp.append(2*t-s)\n",
    "        for i in range(len(dp)-1):\n",
    "            if dp[i]>=0:\n",
    "                res+=1\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplitArray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        prefix = [nums[0]]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            prefix.append(nums[i] + prefix[-1])\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(n - 1):\n",
    "            left_section = prefix[i]\n",
    "            right_section = prefix[-1] - prefix[i]\n",
    "            if left_section >= right_section:\n",
    "                res += 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplitArray(self, nums: List[int]) -> int:\n",
    "        presum=[0]\n",
    "        n,c=len(nums),0\n",
    "        for i in range(n-1):\n",
    "            presum.append(presum[-1]+nums[i])\n",
    "        presum.append(sum(nums))\n",
    "        for j in range(n-1):\n",
    "            if presum[j+1] >= presum[-1]/2:\n",
    "                c+=1\n",
    "        return c\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplitArray(self, nums: List[int]) -> int:\n",
    "        presum=[0]\n",
    "        n,c=len(nums),0\n",
    "        for i in range(n-1):\n",
    "            presum.append(presum[-1]+nums[i])\n",
    "        presum.append(sum(nums))\n",
    "        for j in range(n-1):\n",
    "            if presum[j+1] >= presum[-1]/2:\n",
    "                c+=1\n",
    "        return c\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplitArray(self, nums: List[int]) -> int:\n",
    "        S = sum(nums)\n",
    "        prefix = [0]\n",
    "        for i in nums:\n",
    "            prefix.append(prefix[-1]+i)\n",
    "        res = 0\n",
    "        for i in range(len(nums)-1):\n",
    "            if prefix[i+1] >= S - prefix[i+1]:res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplitArray(self, nums: List[int]) -> int:\n",
    "        presum=[0]\n",
    "        n,c=len(nums),0\n",
    "        for i in range(n-1):\n",
    "            presum.append(presum[-1]+nums[i])\n",
    "        presum.append(sum(nums))\n",
    "        for j in range(n-1):\n",
    "            if presum[j+1] >= presum[-1]/2:\n",
    "                c+=1\n",
    "        return c\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplitArray(self, nums: List[int]) -> int:\n",
    "        psum = [0]\n",
    "        for num in nums:\n",
    "            psum.append(psum[-1] + num)\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(n-1):\n",
    "            if  psum[i+1] >= psum[-1] - psum[i+1]:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplitArray(self, nums: List[int]) -> int:\n",
    "        s, n, ans = sum(nums), len(nums), 0\n",
    "        preSum = [0 for _ in range(n)]\n",
    "        preSum[0] = nums[0]\n",
    "        if preSum[0] * 2 >= s: ans += 1\n",
    "        for i in range(1, n):\n",
    "            preSum[i] = preSum[i-1] + nums[i]\n",
    "            if preSum[i] * 2 >= s and i != n-1:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplitArray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        prefix = [0 for _ in range(n)]\n",
    "        prefix[0] = nums[0]\n",
    "        for i in range(1, n):\n",
    "            prefix[i] = prefix[i-1] + nums[i]\n",
    "        total = sum(nums)\n",
    "        count = 0\n",
    "        for i in range(n-1):\n",
    "            if prefix[i] >= total - prefix[i]:\n",
    "                count += 1\n",
    "        return count"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
